The present invention relates to error correction coding. In particular it relates to error correction by using check symbols which determine a relation between data symbols, created by applying n-valued logic functions to data symbols.
A check symbol over data bits is usually called a parity bit and is used in binary error correction or detection. It is calculated by applying a binary logic function to a number of data bits is for instance a word or sequence of bits. A parity bit is transmitted with the data bits. At the receiving side the parity bit is recalculated using the same function and data bits in identical positions in the codeword or sequence of data bits. If the received parity bit and the calculated parity bit are different one may assume that an error has occurred in at least one bit, including the parity bit.
The number of binary functions that can be applied to calculate a parity bit, and be used to correct errors, is limited to two functions, the binary XOR and EQUAL functions. As both functions are each others reverse, it does generally not make a difference if one uses one or the other.
Because of the limited number of parity functions one has to increase the number of parity bits, and thus lower the information transmission rate, to perform error correction.
N-valued codes, such as Reed-Solomon codes are known. Check symbols are generated by using in essence adders and multipliers in a Linear Feedback Shift Register. Also checksum approaches are known. Essentially all these codes go back to using binary methods and intermediary steps are required in RS codes to determine a check symbol. Like in a RS code one may add symbols to an n-valued codeword according to a coding scheme to improve the Hamming distance between codewords. However detecting and correcting errors may become quite elaborate.
Accordingly simple methods and apparatus providing a greater number of parity functions, lowering the number of check symbols and thus increasing the information transmission rate of error correcting codes or making error correction easier are required.